package com.snopy.leetcode.index1_1000.index101_200;

import com.snopy.leetcode.TreeNode;
import com.snopy.utils.DataFactoryUtil;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question108
 * @description 将有序数组转换为二叉搜索树 easy
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树
 * @email 77912204@qq.com
 * @date 2022/04/21 21:32
 */
public class Question108 {
    public static void main(String[] args) {
        int[] nums = new int[]{-10,-3,0,5,9};
        TreeNode tree = sortedArrayToBST(nums);
        System.out.println(DataFactoryUtil.traver(tree));
    }
    public static TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums,0,nums.length-1);
    }
    private static TreeNode buildBST(int[] nums,int l,int r){
        if (l > r){
            return null;
        }
        int mid = (l + r) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = buildBST(nums,l,mid-1);
        node.right = buildBST(nums,mid+1,r);
        return node;
    }

}
